#
# @lc app=leetcode.cn id=322 lang=python3
#
# [322] 零钱兑换
#

# @lc code=start
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp数组,初始化无穷大,默认拼不出.
        # dp数组含义,dp[i]表示i元最少用dp[i]枚硬币拼出.
        dp = [float('inf') for _ in range(amount+1)]
        dp[0] = 0 # 0枚硬币拼出0元
        
        for coin in coins:
            # print(coin, end=' ')
            for i in range(coin, amount+1):
                dp[i] = min(dp[i-coin]+1, dp[i])
                # print(f'dp[{i}]={dp[i]}', end=' ')
            # print()
                
        return dp[amount] if dp[amount]!=float('inf') else -1
        
# @lc code=end

